package com.lw.leetcode.greedy.c;

/**
 * Created with IntelliJ IDEA.
 * 517. 超级洗衣机
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/29 9:48
 */
public class FindMinMoves {

    public static void main(String[] args) {
        FindMinMoves test = new FindMinMoves();

        // 3
//        int[] arr = {1,0,5};

        // 2
//        int[] arr = {0,3,0};

        // 2
//        int[] arr = {0, 0, 3};

        // 2
//        int[] arr = {4, 0, 0, 4};

        // 18
//        int[] arr = {10, 20, 0, 0, 0};

        // 18
//        int[] arr = {0, 0, 0, 10, 20};

        // 14
        int[] arr = {0, 10, 20, 0, 0};

        //
//        int length = 10000;
//        int[] arr = Utils.getArr(length, 0, 100000);
//        int sum = 0;
//        for (int i : arr) {
//            sum += i;
//        }
//        sum -= arr[length - 1];
//        arr[length - 1] = length - sum % length;
//        System.out.println();
//        System.out.println(Arrays.toString(arr));


        int minMoves = test.findMinMoves(arr);
        System.out.println(minMoves);
    }

    public int findMinMoves(int[] machines) {
        int sum = 0;
        for (int machine : machines) {
            sum += machine;
        }
        int length = machines.length;
        if (sum % length != 0) {
            return -1;
        }
        int p = sum / length;
        int max = 0;
        int s = 0;
        int s1 = 0;
        for (int i = 0; i < length; i++) {
            int m = machines[i] - p;
            if (s >= 0) {
                max = Math.max(max, (m + s));
            } else {
                max = Math.max(max, m);
            }
            s += m;

            m = machines[length - 1 - i] - p;
            if (s1 >= 0) {
                max = Math.max(max, (m + s1));
            } else {
                max = Math.max(max, m);
            }
            s1 += m;
        }
        return max;
    }

}
